{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Lowest Common Ancestor of Deepest Leaves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #hash-table #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #哈希表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lcaDeepestLeaves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最深叶节点的最近公共祖先"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个有根节点<meta charset=\"UTF-8\" />&nbsp;<code>root</code>&nbsp;的二叉树，返回它&nbsp;<em>最深的叶节点的最近公共祖先</em>&nbsp;。</p>\n",
    "\n",
    "<p>回想一下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>叶节点</strong> 是二叉树中没有子节点的节点</li>\n",
    "\t<li>树的根节点的&nbsp;<strong>深度&nbsp;</strong>为&nbsp;<code>0</code>，如果某一节点的深度为&nbsp;<code>d</code>，那它的子节点的深度就是&nbsp;<code>d+1</code></li>\n",
    "\t<li>如果我们假定 <code>A</code> 是一组节点&nbsp;<code>S</code>&nbsp;的 <strong>最近公共祖先</strong>，<code>S</code>&nbsp;中的每个节点都在以 <code>A</code> 为根节点的子树中，且 <code>A</code>&nbsp;的深度达到此条件下可能的最大值。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/01/sketch1.png\" style=\"height: 340px; width: 400px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,5,1,6,2,0,8,null,null,7,4]\n",
    "<strong>输出：</strong>[2,7,4]\n",
    "<strong>解释：</strong>我们返回值为 2 的节点，在图中用黄色标记。\n",
    "在图中用蓝色标记的是树的最深的节点。\n",
    "注意，节点 6、0 和 8 也是叶节点，但是它们的深度是 2 ，而节点 7 和 4 的深度是 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>[1]\n",
    "<strong>解释：</strong>根节点是树中最深的节点，它是它本身的最近公共祖先。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [0,1,3,null,2]\n",
    "<strong>输出：</strong>[2]\n",
    "<strong>解释：</strong>树中最深的叶节点是 2 ，最近公共祖先是它自己。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数将在<meta charset=\"UTF-8\" />&nbsp;<code>[1, 1000]</code>&nbsp;的范围内。</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 1000</code></li>\n",
    "\t<li>每个节点的值都是&nbsp;<strong>独一无二</strong>&nbsp;的。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题与力扣 865 重复：<a href=\"https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/\">https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [lowest-common-ancestor-of-deepest-leaves](https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [lowest-common-ancestor-of-deepest-leaves](https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,5,1,6,2,0,8,null,null,7,4]', '[1]', '[0,1,3,null,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return [0, None]\n",
    "            leftHeight, leftLCA = helper(root.left)\n",
    "            rightHeight, rightLCA = helper(root.right)\n",
    "            if leftHeight > rightHeight:\n",
    "                return leftHeight + 1, leftLCA\n",
    "            if leftHeight < rightHeight:\n",
    "                return rightHeight + 1, rightLCA\n",
    "            return leftHeight + 1, root\n",
    "        return helper(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return []\n",
    "        res = []\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            tmp = []\n",
    "            next_stack = []\n",
    "            for node in stack:\n",
    "                tmp.append(node)\n",
    "                if node.left:\n",
    "                    next_stack.append(node.left)\n",
    "                if node.right:\n",
    "                    next_stack.append(node.right)\n",
    "            if next_stack:\n",
    "                stack = next_stack\n",
    "            else:\n",
    "                res = tmp\n",
    "                break\n",
    "        if len(res) == 1:\n",
    "            return res[0]\n",
    "        else:\n",
    "            r1, r2 = res[0], res[-1]\n",
    "        return self.findfather(root,r1,r2)\n",
    "\n",
    "    def findfather(self, root, root1, root2):\n",
    "        if root is None:\n",
    "            return None\n",
    "        if root.val == root1.val or root.val == root2.val:\n",
    "            return root\n",
    "        l = self.findfather(root.left, root1, root2)\n",
    "        r = self.findfather(root.right, root1, root2)\n",
    "        if l and r:\n",
    "            return root\n",
    "        else:\n",
    "            return l if r is None else r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        # Step 1. 先記錄各node的深度，以及最大深度\n",
    "        dict_depth = {}\n",
    "        def dfs(node, depth):\n",
    "            if node == None:\n",
    "                return\n",
    "            dict_depth[node] = depth\n",
    "            dfs(node.left, depth + 1)\n",
    "            dfs(node.right, depth + 1)\n",
    "\n",
    "        dfs(root, 0)\n",
    "        max_depth = 0\n",
    "        for value in dict_depth.values():\n",
    "            if value > max_depth:\n",
    "                max_depth = value\n",
    "        print(max_depth)\n",
    "        \n",
    "        # Step 2. 取出包含所有最深節點的父節點\n",
    "        def dfs2(node):\n",
    "            if node == None:\n",
    "                return None\n",
    "\n",
    "            left_node = dfs2(node.left)\n",
    "            right_node = dfs2(node.right)\n",
    "            if (left_node != None) and (right_node != None):\n",
    "                return node\n",
    "            elif left_node != None:\n",
    "                return left_node\n",
    "            elif right_node != None:\n",
    "                return right_node \n",
    "            elif dict_depth[node] == max_depth:\n",
    "                return node\n",
    "            else:\n",
    "                return None\n",
    "\n",
    "        return dfs2(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:\n",
    "        if not root: return root\n",
    "        self.res = None\n",
    "        self.maxDepth = -1\n",
    "        def helper(root=root, depth=0):\n",
    "            if not root: return depth\n",
    "            left = helper(root.left, depth + 1)\n",
    "            right = helper(root.right, depth + 1)\n",
    "            if left == right and left >= self.maxDepth:\n",
    "                self.res = root\n",
    "                self.maxDepth = left\n",
    "            return max(left, right)\n",
    "        helper()\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None, 0\n",
    "            l_res, l_dep = dfs(root.left)\n",
    "            r_res, r_dep = dfs(root.right)\n",
    "            if l_dep == r_dep:\n",
    "                return root, l_dep+1\n",
    "            if l_dep > r_dep:\n",
    "                return l_res, l_dep+1\n",
    "            else:\n",
    "                return r_res, r_dep+1\n",
    "        data = dfs(root)\n",
    "        return data[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:\n",
    "        def height(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(height(root.left), height(root.right))+1\n",
    "        \n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            left = height(root.left)\n",
    "            right = height(root.right)\n",
    "            if left>right:\n",
    "                return dfs(root.left)\n",
    "            elif left<right:\n",
    "                return dfs(root.right)\n",
    "            else:\n",
    "                return root\n",
    "        \n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root: TreeNode):\n",
    "            if not root:\n",
    "                return None, 0\n",
    "            left, left_length = dfs(root.left)\n",
    "            right, right_length = dfs(root.right)\n",
    "            if left_length == right_length:\n",
    "                return root, left_length + 1\n",
    "            elif left_length > right_length:\n",
    "                return left, left_length + 1\n",
    "            else:\n",
    "                return right, right_length + 1\n",
    "\n",
    "        ans, _ = dfs(root)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        deepest = []\n",
    "        queue = collections.deque([root])\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            deepest = list(queue)\n",
    "            for _ in range(length):\n",
    "                node = queue.popleft()\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                \n",
    "        if len(deepest) == 1:\n",
    "            return deepest[0]\n",
    "        deepest = set(deepest)\n",
    "        res = None\n",
    "        \n",
    "        def dfs(root):\n",
    "            nonlocal res \n",
    "            if not root:\n",
    "                return set()\n",
    "            \n",
    "            ans = set()\n",
    "            if root in deepest:\n",
    "                ans.add(root)\n",
    "            ans |= dfs(root.left)\n",
    "            ans |= dfs(root.right)\n",
    "            if not res and ans == deepest:\n",
    "                res = root \n",
    "            return ans \n",
    "        \n",
    "        dfs(root)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.depthCache = {}\n",
    "\n",
    "    def getDepth(self, node: TreeNode) -> int:\n",
    "        if node is None:\n",
    "            return 0\n",
    "        if node.val in self.depthCache:\n",
    "            return self.depthCache[node.val]\n",
    "        val = 1 + max(self.getDepth(node.left), self.getDepth(node.right))\n",
    "        self.depthCache[node.val] = val\n",
    "        return val\n",
    "\n",
    "    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:\n",
    "        leftDep = self.getDepth(root.left)\n",
    "        rightDep = self.getDepth(root.right)\n",
    "        if leftDep == rightDep:\n",
    "            return root\n",
    "        return self.lcaDeepestLeaves(root.left) if leftDep > rightDep else self.lcaDeepestLeaves(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:\n",
    "        dic = {\n",
    "            'dep' : 0,\n",
    "            'path' : []\n",
    "        }\n",
    "\n",
    "        def dfs(root, dep, ans_path):\n",
    "            if (root == None):\n",
    "                return\n",
    "            # print(root.val, dep, ans_path)\n",
    "            new_ans_path = [root]\n",
    "            new_ans_path.extend(ans_path)\n",
    "            # print(new_ans_path)\n",
    "            if (dep > dic['dep']) :\n",
    "                dic['path'] = [new_ans_path]\n",
    "                dic['dep'] = dep\n",
    "            elif (dep == dic['dep']):\n",
    "                dic['path'].append(new_ans_path)\n",
    "            dfs(root.left, dep+1, new_ans_path)\n",
    "            dfs(root.right, dep+1, new_ans_path)\n",
    "        dfs(root, 0 , [])\n",
    "        if (root == None):\n",
    "            return None\n",
    "        \n",
    "        def findAns(paths):\n",
    "            print(len(paths))\n",
    "            if paths == None or len(paths) == 0:\n",
    "                return None\n",
    "            if (paths == 1):\n",
    "                return paths[0][0]\n",
    "            #paths >=2 找共同祖先\n",
    "            ans = None\n",
    "            first = paths[0]\n",
    "            for node in first:\n",
    "                is_ans = True\n",
    "                for path in paths[1:]:\n",
    "                    has_node = False\n",
    "                    for j in path:\n",
    "                        print(node.val, j.val)\n",
    "                        if (j.val == node.val):\n",
    "                            has_node = True\n",
    "                            break\n",
    "                    print(has_node)\n",
    "                    if has_node == False:\n",
    "                        is_ans = False\n",
    "                if is_ans == True:\n",
    "                    ans = node\n",
    "                    break\n",
    "            \n",
    "            return ans\n",
    "        node = findAns(dic['path'])\n",
    "        return node\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:        \n",
    "        if not root:\n",
    "            return root\n",
    "        memory = [root]\n",
    "        while True:\n",
    "            next_memory = []\n",
    "            for node in memory:\n",
    "                if node.left:\n",
    "                    node.left.parent = node\n",
    "                    next_memory.append(node.left)\n",
    "                if node.right:\n",
    "                    node.right.parent = node\n",
    "                    next_memory.append(node.right)\n",
    "            if next_memory:\n",
    "                memory = next_memory\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        while True:\n",
    "            if len(memory) == 1:\n",
    "                return memory[0]\n",
    "            next_memory = []\n",
    "            id_set = set()            \n",
    "            for node in memory:\n",
    "                parent = node.parent\n",
    "                if id(parent) not in id_set:\n",
    "                    id_set.add(id(parent))\n",
    "                    next_memory.append(parent)\n",
    "            memory = next_memory\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:\n",
    "        class TreeNode:\n",
    "            def __init__(self, x):\n",
    "                self.father = x\n",
    "        l = dict()\n",
    "        def find(root,count):\n",
    "            if l.get(count):\n",
    "                l[count].add(root)\n",
    "            else:\n",
    "                l[count] = {root} \n",
    "            if root.left:\n",
    "                root.left.father = root\n",
    "                find(root.left,count + 1)\n",
    "            if root.right:\n",
    "                root.right.father = root\n",
    "                find(root.right,count + 1)\n",
    "        find(root,1)\n",
    "        d = list(l[max(l)])\n",
    "        while len(d) > 1:\n",
    "            d = list(d)\n",
    "            n = len(d)\n",
    "            for i in range(n):\n",
    "                d.append(d[i].father)\n",
    "            d = set(d[n:])\n",
    "        for i in d:\n",
    "            d = i\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:\n",
    "        if root == None:return root\n",
    "        dict={}\n",
    "        #为dict添加数据\n",
    "        def dfs(tree,idx):\n",
    "            if tree==None:return idx\n",
    "            temp = max(dfs(tree.right,idx+1),dfs(tree.left,idx+1))\n",
    "            dict[\"%s\"%(tree)]=temp\n",
    "            return temp\n",
    "        dfs(root,0)\n",
    "        while True:\n",
    "            if root.left==None and root.right==None:return root\n",
    "            if root.left==None:\n",
    "                root=root.right\n",
    "                continue\n",
    "            if root.right == None: \n",
    "                root = root.left\n",
    "                continue\n",
    "            left=dict[\"%s\"%(root.left)]\n",
    "            right=dict[\"%s\"%(root.right)]\n",
    "            if left==right:return root\n",
    "            if left>right:\n",
    "                root=root.left\n",
    "            else:\n",
    "                root=root.right\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def recur(root):\n",
    "            if not root: return -1, None\n",
    "            l, r = recur(root.left), recur(root.right)\n",
    "            \n",
    "            if l[0] < r[0]: return r[0] + 1, r[1]\n",
    "            if l[0] > r[0]: return l[0] + 1, l[1]\n",
    "            if l[0] == r[0]: return l[0] + 1, root\n",
    "        \n",
    "        return recur(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        max_depth = 0\n",
    "        max_paths = []\n",
    "        def dfs(node, path, depth):\n",
    "            nonlocal max_depth, max_paths\n",
    "\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            path.append(node)\n",
    "            if not node.left and not node.right:\n",
    "                if depth > max_depth:\n",
    "                    max_paths = [path.copy()]\n",
    "                    max_depth = depth\n",
    "                elif depth == max_depth:\n",
    "                    max_paths.append(path.copy())\n",
    "                path.pop()\n",
    "                return\n",
    "\n",
    "            dfs(node.left, path, depth + 1)\n",
    "            dfs(node.right, path, depth + 1)\n",
    "            path.pop()\n",
    "\n",
    "        dfs(root, [], 0)\n",
    "        nodes_set = set(max_paths[0])\n",
    "        for i in range(1, len(max_paths)):\n",
    "            nodes_set.intersection_update(set(max_paths[i]))\n",
    "        return max_paths[0][len(nodes_set) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(root,deep):\n",
    "            if not root:\n",
    "                return (root,deep)\n",
    "            l=dfs(root.left,deep+1)\n",
    "            r=dfs(root.right,deep+1)\n",
    "            if l[1]<r[1]:\n",
    "                return r\n",
    "            if l[1]>r[1]:\n",
    "                return l\n",
    "            else:\n",
    "                return (root,l[1])\n",
    "        ret=dfs(root,0)\n",
    "        return ret[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        Result = collections.namedtuple(\"Result\", (\"node\", \"dist\"))\n",
    "        def dfs(node):\n",
    "            # Return the result of the subtree at this node.\n",
    "            if not node: return Result(None, 0)\n",
    "            L, R = dfs(node.left), dfs(node.right)\n",
    "            if L.dist > R.dist: return Result(L.node, L.dist + 1)\n",
    "            if L.dist < R.dist: return Result(R.node, R.dist + 1)\n",
    "            return Result(node, L.dist + 1)\n",
    "\n",
    "        return dfs(root).node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:\n",
    "        # max_n :int = 0\n",
    "        d = {}\n",
    "        ans = None\n",
    "        def d_s(root):\n",
    "            nonlocal d\n",
    "            if root == None:\n",
    "                return 1\n",
    "            else:\n",
    "                le = d_s(root.left)\n",
    "                ri = d_s(root.right)\n",
    "                d[root.val] = [le,ri]\n",
    "                return max(le,ri)+1\n",
    "        def s_t(root):\n",
    "            nonlocal ans\n",
    "            nonlocal d\n",
    "            # if root.val in d.keys():\n",
    "            le = d[root.val][0]\n",
    "            ri = d[root.val][1]\n",
    "            # else:\n",
    "            #     le = d_s(root.left)\n",
    "            #     ri = d_s(root.right)\n",
    "            if  le == ri :\n",
    "                ans = root\n",
    "            else:\n",
    "                if le > ri:\n",
    "                    s_t(root.left)\n",
    "                else:\n",
    "                    s_t(root.right)\n",
    "        d_s(root)\n",
    "        s_t(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(root):\n",
    "            if root == None:\n",
    "                return 0, None\n",
    "            d1, left = dfs(root.left)\n",
    "            d2, right = dfs(root.right)\n",
    "            if d1 > d2:\n",
    "                return d1 + 1, left\n",
    "            if d2 > d1:\n",
    "                return d2 + 1, right\n",
    "            return d1 + 1, root\n",
    "\n",
    "        return dfs(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        ans, max_depth = None, 0\n",
    "        def dfs(node, depth):\n",
    "            nonlocal ans, max_depth\n",
    "            if node is None:\n",
    "                max_depth = max(depth, max_depth)\n",
    "                return depth \n",
    "\n",
    "            depth += 1\n",
    "            left_max_depth = dfs(node.left, depth)\n",
    "            right_max_depth = dfs(node.right, depth)\n",
    "            if left_max_depth == right_max_depth == max_depth:\n",
    "                ans = node \n",
    "            return max(left_max_depth, right_max_depth)\n",
    "\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1\n",
    "\n",
    "    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        l_depth = self.maxDepth(root.left)\n",
    "        r_depth = self.maxDepth(root.right)\n",
    "        if l_depth == r_depth:\n",
    "            return root\n",
    "        elif l_depth > r_depth:\n",
    "            return self.lcaDeepestLeaves(root.left)\n",
    "        else:\n",
    "            return self.lcaDeepestLeaves(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        ans = None\n",
    "        max_depth = -1\n",
    "        def dfs(node, depth):\n",
    "            nonlocal ans, max_depth\n",
    "            if node is None:\n",
    "                max_depth = max(max_depth, depth)\n",
    "                return depth\n",
    "            l_max_depth = dfs(node.left, depth + 1)\n",
    "            r_max_depth = dfs(node.right, depth + 1)\n",
    "            if l_max_depth == r_max_depth == max_depth:\n",
    "                ans =  node\n",
    "            return max(l_max_depth, r_max_depth)\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
